P2341 [HAOI2006]受欢迎的牛

这道题一看就是一道强连通分量的题,不会的可以参考我的博客

当我们用TarjanTarjan缩点之后,记新图点的个数为cntcnt。我们枚举原图的每一条边,计算新图中的点的出度。对于点ii,我们把它的出度记为Out[i]Out[i]。那么,会有以下几种情况:

1.没有一个Out[i]Out[i]为0,说明每一个点至少有一条连向其他边的有向边,那么新图至少有cntcnt条边,一定会有一个环(因为cnt1cnt-1条边是一棵树,无论如何加边都会构成环),但缩点后不可能有环,矛盾。

2.只有一个Out[i]Out[i]为0,那么这个点一定受到所有奶牛的膜拜,(其他奶牛出度不为0,会膜拜其他奶牛,这样膜来膜去一定会汇集到出度为0的奶牛上,不理解的自行脑补一下

3.有两个及以上的Out[i]Out[i]为0,那么每个人至少得不到一群奶牛(已经缩点,可能不止一头)的支持。直接输出0。

综合以上三点,我们就可以写出正解了:

#include <cstdio>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;

const int MAXN = 10000;
int n,m,x,y;
vector< int > Graph[ MAXN + 5 ];
vector< int > lit_Graph[ MAXN + 5 ];
stack< int > s;

int dfn[ MAXN + 5 ] , low[ MAXN + 5 ] , depth , cnt;
int belong[ MAXN + 5 ] , num[ MAXN + 5 ] , Out[ MAXN + 5 ];
bool is[ MAXN + 5 ];
void Tarjan( int u ) {
    dfn[ u ] = low[ u ] = ++ depth;
    is[ u ] = 1 , s.push( u );

    int v;
    for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
        v = Graph[ u ][ i ];
        if( !dfn[ v ] ) {
            Tarjan( v );
            low[ u ] = min( low[ u ] , low[ v ] );
        }
        else if( is[ v ] )
            low[ u ] = min( low[ u ] , dfn[ v ] );
    }
    if( dfn[ u ] == low[ u ] ) {
        cnt ++;
        do{
            v = s.top( );
            is[ v ] = 0 , s.pop( );
            belong[ v ] = cnt;
            num[ cnt ] ++;
        }while( u != v );
    }
}

int main( ) {
    scanf("%d %d",&n,&m);
    for( int i = 1 ; i <= m ; i ++ ) {
        scanf("%d %d",&x,&y);
        Graph[ x ].push_back( y );
    }
    for( int i = 1 ; i <= n ; i ++ )
        if( !dfn[ i ] ) Tarjan( i );
    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 0 ; j < Graph[ i ].size( ) ; j ++ ) {
            int u = belong[ i ] , v = belong[ Graph[ i ][ j ] ];
            if( u != v ) {
                lit_Graph[ u ].push_back( v );
                Out[ u ] += num[ v ];
            }
        }
    int Ans = 0 , tot = 0;
    for( int i = 1 ; i <= cnt ; i ++ )
        if( Out[ i ] == 0 ) Ans += num[ i ] , tot ++;
    printf("%d",tot >= 2 ? 0 : Ans);
    return 0;
}